https://www.slideshare.net/mobile/shindannin/project-selection-problem

  • bury in the fire   minimum cut Burn bury?
  • Multiple sub-problems, choices, and costs depending on the choice.
  • There is a dependency on the choice of subproblems.
  • If the number of problems is about 20, you can solve it with a full search.
    • It can be solved by attributing it to the smallest cut when it’s 10000 or something. How is it different from →DP?

I think it’s time for the concept of ‘burn fill’ to go away. Because if you remember the form of Project Selection itself, it’s a blink of an eye. http://tokoharuland.hateblo.jp/entry/2017/11/12/234636 http://tokoharuland.hateblo.jp/entry/2017/12/25/000003 Project Selection Problem


This page is auto-translated from /nishio/最小カットを使って「燃やす埋める問題」を解く using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.